package com.sheng.leetcode.year2022.month08.day25;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/08/25
 *
 * 658. 找到 K 个最接近的元素
 *
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 * 整数 a 比整数 b 更接近 x 需要满足：
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 *
 * 示例 1：
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 *
 * 示例 2：
 * 输入：arr = [1,2,3,4,5], k = 4, x = -1
 * 输出：[1,2,3,4]
 *
 * 提示：
 *
 * 1 <= k <= arr.length
 * 1 <= arr.length <= 104
 * arr 按 升序 排列
 * -104 <= arr[i], x <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-k-closest-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0658 {

    @Test
    public void test01() {
//        int[] arr = {1,2,3,4,5};
//        int k = 4;
//        int x = 3;
//        int[] arr = {1,2,3,4,5};
//        int k = 4;
//        int x = -1;
//        int[] arr = {1,1,1,10,10,10};
//        int k = 1;
//        int x = 9;
//        int[] arr = {-2,-1,1,2,3,4,5};
//        int k = 7;
//        int x = 3;
        int[] arr = {3,5,8,10};
        int k = 2;
        int x = 15;
        System.out.println(new Solution().findClosestElements(arr, k, x));
    }
}
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        int length = arr.length;
        int left = 0;
        int right = 0;
        //获取数组中最接近x的元素的索引，赋给right，索引的前一位赋值给left
        if (x > arr[length - 1]) {
            //如果x比数组中的所有元素都大，那么直接将数组最后的两个元素索引赋给left和right
            left = length - 2;
            right = length - 1;
        } else {
            for (int i = 0; i < length; i++) {
                if (arr[i] >= x) {
                    right = i;
                    left = i - 1;
                    break;
                }
            }
        }
        for (int i = 0; i < k; i++) {
            if (left == -1 && right <= length) {
                right++;
            } else if (right == length && left >= 0) {
                left--;
            } else {
                if (Math.abs(arr[left] - x) < Math.abs(arr[right] - x) || (Math.abs(arr[left] - x) == Math.abs(arr[right] - x) && arr[left] < arr[right])) {
                    left--;
                } else {
                    right++;
                }
            }
        }
        for (int i = left + 1; i < right; i++) {
            list.add(arr[i]);
        }
        return list;
    }
}
